package leetcode.year2021.month10;

/**
 *  101. 对称二叉树
 *
 *  思路： 使用递归，判断root是否是空，不为空的话，判断root的左子树和右子树是否镜像相等
 *  判断方法为，root的左子树的右子树，和root的右子树的左子树，镜像对称
 *             root的左子树的左子树，和root的右子树的右子树，镜像对称
 */
public class _24_02IsSymmetric101 {
  public boolean isSymmetric(TreeNode root) {
    if (root == null){
      return true;
    }
    return dfsJudge(root.left, root.right);
  }

  private Boolean dfsJudge(TreeNode left, TreeNode right) {
    if ((left!=null && right==null) || (left==null && right !=null)){
      return false;
    } else if (left == null && right == null){
      return true;
    } else if (left.val != right.val){
      return false;
    }
    return dfsJudge(left.right,right.left) && dfsJudge(left.left,right.right);
  }

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


  /**
   * 101. 对称二叉树
   *
   * 给定一个二叉树，检查它是否是镜像对称的。
   *
   *  
   *
   * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
   *
   *     1
   *    / \
   *   2   2
   *  / \ / \
   * 3  4 4  3
   *  
   *
   * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
   *
   *     1
   *    / \
   *   2   2
   *    \   \
   *    3    3
   *  
   *
   * 进阶：
   *
   * 你可以运用递归和迭代两种方法解决这个问题吗？
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/symmetric-tree
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   */
}
